#include <stdlib.h>
#include <string.h>

#include "HashTable.h"

HashTable *hash_table_create() {
    HashTable *hash_table    = malloc(sizeof(HashTable));
    hash_table->loadFactor   = DEFAULT_LOAD_FACTOR;
    hash_table->capacity     = DEFAULT_HASH_TABLE_CAPACITY;
    hash_table->threshold    = DEFAULT_HASH_TABLE_CAPACITY * DEFAULT_LOAD_FACTOR;
    hash_table->size         = 0;
    hash_table->keyHash      = hash_table_default_key_hash;
    hash_table->keyCompare   = hash_table_default_key_compare;
    hash_table->keyDestroy   = hash_table_default_key_destroy;
    hash_table->valueDestroy = hash_table_default_value_destroy;
    hash_table->valueDup     = hash_table_default_value_dup;
    hash_table->table        = malloc(sizeof(Entry *) * hash_table->capacity);
    for (int i = 0; i < hash_table->capacity; i++) {
        hash_table->table[i] = NULL;
    }
    return hash_table;
}

void hash_table_destroy(HashTable *hash_table) {
    for (int i = 0; i < hash_table->capacity; i++) {
        if (hash_table->table[i] == NULL)
            return;
        hash_table_entry_destroy(hash_table, hash_table->table[i]);
    }
    free(hash_table);
}

Entry *hash_table_create_entry(void *key, void *value) {
    Entry *entry = malloc(sizeof(Entry));
    entry->key   = key;
    entry->value = value;
    entry->next  = NULL;
    return entry;
}

void hash_table_entry_destroy(HashTable *hash_table, Entry *entry) {
    hash_table->keyDestroy(entry->key);
    hash_table->valueDestroy(entry->value);
    free(entry);
}

/**
 * 重置 entry
 * 全部成员变量置为 NULL, 不会释放内存
 */
void hash_table_entry_reset(Entry *entry) {
    entry->key   = NULL;
    entry->value = NULL;
    entry->next  = NULL;
}

/**
 * 添加元素
 * @note 不会进行拷贝
 */
void hash_table_put(HashTable *hash_table, void *key, void *value) {
    int    idx   = hash_table->keyHash(key) & (hash_table->capacity - 1);
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        hash_table->table[idx] = hash_table_create_entry(key, value);
    } else {
        Entry *head = hash_table_create_entry(NULL, NULL);
        Entry *p    = head;
        p->next     = entry;
        while (p->next != NULL) {
            if (hash_table->keyCompare(p->next->key, key) == 0) {
                free(p->next->value); // 进行了覆盖, 释放旧的value
                p->next->value = value;
                free(head);
                return;
            }
            p = p->next;
        }
        p->next = hash_table_create_entry(key, value);
        free(head);
    }
    hash_table->size++;
    if (hash_table->size > hash_table->threshold) {
        hash_table_resize(hash_table);
    }
}

int hash_table_have(HashTable *hash_table, void *key) {
    int    idx   = hash_table->keyHash(key) & hash_table->capacity - 1;
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        return 0;
    }
    while (entry != NULL) {
        if (hash_table->keyCompare(key, entry->key) == 0) {
            return 1;
        }
        entry = entry->next;
    }
    return 0;
}

void *hash_table_get(HashTable *hash_table, void *key) {
    int    idx   = hash_table->keyHash(key) & hash_table->capacity - 1;
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        return NULL;
    }
    while (entry != NULL) {
        if (hash_table->keyCompare(key, entry->key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return NULL;
}

void hash_table_full_remove(HashTable *hash_table, void *key) {
    int    idx   = hash_table->keyHash(key) & hash_table->capacity - 1;
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        return;
    }

    Entry *head = hash_table_create_entry(NULL, NULL);
    Entry *p    = head;
    p->next     = entry;
    while (p->next != NULL) {
        if (hash_table->keyCompare(key, p->next->key) == 0) {
            Entry *temp = p->next;
            p->next     = p->next->next;
            hash_table->size--;
            hash_table_entry_destroy(hash_table, temp);
            break;
        }
        p = p->next;
    }
    hash_table->table[idx] = head->next;
    free(head);
}

void hash_table_remove(HashTable *hash_table, void *key) {
    int    idx   = hash_table->keyHash(key) & hash_table->capacity - 1;
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        return;
    }

    Entry *head = hash_table_create_entry(NULL, NULL);
    Entry *p    = head;
    p->next     = entry;
    while (p->next != NULL) {
        if (hash_table->keyCompare(key, p->next->key) == 0) {
            p->next = p->next->next;
            hash_table->size--;
            break;
        }
        p = p->next;
    }
    hash_table->table[idx] = head->next;
    free(head);
}

void *hash_table_pop(HashTable *hash_table, void *key) {
    void  *value = NULL;
    int    idx   = hash_table->keyHash(key) & hash_table->capacity - 1;
    Entry *entry = hash_table->table[idx];
    if (entry == NULL) {
        return NULL;
    }

    Entry *head = hash_table_create_entry(NULL, NULL);
    Entry *p    = head;
    p->next     = entry;
    while (p->next != NULL) {
        if (hash_table->keyCompare(key, p->next->key) == 0) {
            Entry *temp = p->next;
            value       = hash_table->valueDup(temp->value);
            p->next     = p->next->next;
            hash_table->size--;
            hash_table_entry_destroy(hash_table, temp);
            break;
        }
        p = p->next;
    }
    hash_table->table[idx] = head->next;
    free(head);

    return value;
}

void hash_table_resize(HashTable *hash_table) {
    Entry *head1 = hash_table_create_entry(NULL, NULL), *head2 = hash_table_create_entry(NULL, NULL);
    Entry *p1, *p2;
    int    oldCapacity = hash_table->capacity;
    int    newCapacity = oldCapacity << 1;

    // 还未处理realloc失败的情况
    hash_table->table = realloc(hash_table->table, sizeof(Entry *) * newCapacity);
    for (int i = oldCapacity; i < newCapacity; i++) {
        hash_table->table[i] = NULL;
    }

    for (int i = 0; i < oldCapacity; i++) {
        Entry *p = hash_table->table[i];
        if (p == NULL)
            continue;

        hash_table_entry_reset(head1);
        hash_table_entry_reset(head2);
        p1 = head1;
        p2 = head2;

        while (p != NULL) {
            if ((hash_table->keyHash(p->key) & oldCapacity) == 0) {
                p1->next = p;
                p1       = p;
            } else {
                p2->next = p;
                p2       = p;
            }
            p = p->next;
        }
        p1->next                           = NULL;
        hash_table->table[i]               = head1->next;
        p2->next                           = NULL;
        hash_table->table[i + oldCapacity] = head2->next;
    }
    hash_table->capacity  = newCapacity;
    hash_table->threshold = newCapacity * hash_table->loadFactor;

    free(head1);
    free(head2);
}

int hash_table_get_size(HashTable *hash_table) { return hash_table->size; }

int hash_table_default_key_compare(const void *key1, const void *key2) { return strcmp(key1, key2); }

int hash_table_default_key_hash(const void *key) {
    const char *data = key;
    int         hash = 0;
    for (int i = 0; i < strlen(data); i++) {
        hash = 31 * hash + data[i];
    }
    return hash;
}

void hash_table_default_key_destroy(void *key) { free(key); }

void hash_table_default_value_destroy(void *value) { free(value); }

void *hash_table_default_value_dup(void *value) {
    char *value_dup = malloc(strlen(value) + 1);
    strcpy(value_dup, value);

    return value_dup;
}